package com.example.sqrt;

/**
 * 在不使用sqrt()函数的情况下，对x进行开方计算，取得x的平方根的整数部分
 * 二分法(例如2的开方，得到的结果一定在2到x-1直接的某个值)
 * i * i < x
 * (i + 1) * (i + 1) > x
 * 那么平方根的值介于i到i+1直接，我们需要找i和i+1那个值更接近于x
 */
public class Dichotomy {

    // 二分查找
    public static int binarySearch(int x) {
        int index = -1;// -1错误值
        int left = 0;// 左指针
        int right = x;// 右指针
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid * mid <= x) {
                index = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index;
    }

    public static void main(String[] args) {

        System.out.println(binarySearch(24));

    }

}
